package 链表算法题;

public class 链表相交 {
    class Solution{
        public ListNode getIntersectionNode(ListNode headA,ListNode headB){
              //计算各自的长度
            ListNode currA = headA;
            ListNode currB = headB;
            int lenA=0,lenB=0;
            while (currA!=null){
                lenA++;
                currA = currA.next;
            }
            while (currB!=null){
                lenB++;
                currB = currB.next;
            }
            //这里算完了还要帮人家返回去原来的值
            currA = headA;
            currB = headB;

            // 让curA为最长链表的头，lenA为其长度
            if (lenB>lenA){
                int tmplen = lenA;
                lenA = lenB;
                lenB = tmplen;

                ListNode tmpNode = currA;
                currA = currB;
                currB = tmpNode;
            }

            //求长度差
            //求长度差的意义是 若A太长 B太短 B完了A还没完 那就用长度差让A指到合适的位置继续和B对比
            int gap = lenA -lenB;
            //// 让curA和curB在同一起点上（末尾位置对齐)
            while (gap-- >0){
                currA = currA.next;
            }
            // 遍历curA 和 curB，遇到相同则直接返回
            while (currA!=null){
                if (currA == currB){
                 return currA;
                }
                currA = currA.next;
                currB = currB.next;
            }
               return null;
        }
    }
}
